package cn.lena.telent;


import org.junit.Test;

import java.util.ArrayList;

class ListNode {
   int val;
   ListNode next = null;
   public ListNode(int val){
   		this.val=val;
   }
 }

public class Main {

	@Test
	public void test2() {
		//int[] arr={3,2,1,0,4};
		int[] arr={1,0,1,0};
		System.out.println(jumpMax(arr));
	}

	// 二面
	public static boolean jumpMax(int[] arr) {
		if(arr.length <= 1) {
			return true;
		}
		int i=0;
		int length=arr.length-1;
		while(i < arr.length) {
			boolean flag=false; // 标志当前循环是否有跳 避免死循环
			// 当前所能跳的最大步数
			int cur=arr[i];
			// 能从当前点跳跃到结尾点(length-i)
			if(cur >= length - i) {
				return true;
			}
			// 当前点不能跳
			if(cur == 0) {
				if(i > 0) {
					// 判断前面的是否能够跳过当前0值
					for(int j=0;j<i;i++) {
						if(arr[j]+j > i) {
							i++;
							flag=true;
							break;
						}
					}
					// 不能跳过则返回false
					if(!flag) {
						return false;
					}
				}
			} else {
				// 考虑为0时，可能在前面可以跳过当前步
				// 每次跳最大步，然后不行就回退一步
				i=cur+i;
				flag=true;
			}
			if(!flag) {
				// 既没有前进 也没有回退
				return false;
			}
		}
		return false;
	}

	// 一面
	public static void main(String[] args) {
		int[] arr={3,2,1,0,4};
		System.out.println(jumpMax(arr));

/*		Scanner in = new Scanner(System.in);
		int num=in.nextInt();
		int k=in.nextInt();        //只输出k行，进行发放广告的数量
		int arr[]=new int[num];
		for(int i=0;i<num;i++){
			arr[i]=in.nextInt();
		}
		while(k!=0){
			int min=100;
			int current=0;
			for(int i=0;i<arr.length;i++){
				if(min>arr[i]){
					min=arr[i];
					current=i;
				}
			}
			System.out.println(current+1);
			arr[current]*=2;
			k--;
		}*/
	}


	//先遍历一次，将每个数字存储在数组中，然后寻找数组中最小的序列段
	ListNode turn(ListNode S) {
		if (S==null)	return null;
		if(S.next==null)	return S;
		ListNode p1 = S;    //在头部
		int count = 0;    //节点个数
		int min = p1.val;
		ListNode minp = null;
		ArrayList<Integer> list = new ArrayList<>();    //存储最小值出现的位置
		list.add(0);
		//将每个值存储起来
		while (p1 != null) {
			if (min > p1.val) {
				min = p1.val;
				minp = p1;
				list = new ArrayList<>();        //清空原先的值
				list.add(count);
			} else if (min == p1.val && p1 != S) {
				minp = null;    //有多个minp
				list.add(count);
			}
			count++;
			p1 = p1.next;
		}
		if (minp == null) {
			//不只一个最小值
			int arr[] = new int[count];
			p1 = S;
			//存储每个节点的值到数组中
			for (int i = 0; i < count; i++) {
				arr[i] = p1.val;
				p1 = p1.next;
			}
			int min1 = list.get(0);
			for (int i = 1; i < list.size() - 1; i++) {
				//比较0，和1处最小值
				int min2 = list.get(i);
				while (true) {
					if (min2 == arr.length) {
						min2 = 0;		//从起点开始
					}
					if(min1 == arr.length)
						min1=0;
					if (arr[min1] > arr[min2]) {
						min1 = list.get(i);
						break;
					} else if (arr[min1] < arr[min2]){
						break;
					}
					min1++;
					min2++;
				}
			}
			min=min1;
			p1 = S;
			count = 0;
			while (p1 != null) {
				if (count == min) {
					minp = p1;
					break;
				}
				p1 = p1.next;
				count++;
			}
		}
		//Test√
		ListNode p = S;
		while (p.next != null) {
			if (p.next == minp) {
				p.next = null;
				break;
			}
			p = p.next;
		}
		p = minp;
		while (minp.next != null) {
			minp = minp.next;
		}
		minp.next = S;
		return p;
	}
}
